package algorithmTopics.stack;

import java.util.*;

/**
 * 解决方案
 *
 * @author 86155
 * @date 2025/06/22
 */
public class Solution {

    /**
     * 出现次数最多的前 K 个元素
     *
     * @param nums nums
     * @param k    k
     * @return {@link int[]}
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 计算不同元素出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.merge(nums[i], 1, Integer::sum);
        }
        //进行排序，用桶来进行排序 装载
        Integer max = Collections.max(map.values());
        List<Integer>[] buckets = new ArrayList[max + 1];
        // 初始化桶
        Arrays.setAll(buckets, i -> new ArrayList<>());
        map.entrySet().forEach( a -> buckets[a.getValue()].add(a.getKey()));
        //倒遍历出答案
        int[] res = new int[k];
        for (int i = max,j = 0; i >= 0 && j < k; i--) {
            for (int x : buckets[i]) {
                res[j++] = x;
            }
        }
        return res;
    }

    /**
     * 查找第K个最大元素
     *
     * @param nums nums
     * @param k    k
     * @return int 数字
     */
    public int findKthLargest(int[] nums, int k) {
        //查找从小到大 第K个元素
        // 启用 快速查找 - 快排
        Random random = new Random();
        return findKthLargestHelper(nums, nums.length - k + 1, random);
    }

    private int findKthLargestHelper(int[] nums, int k, Random random) {

        // 基准值
        int pivotIndex = random.nextInt(nums.length);
        int pivot = nums[pivotIndex];

        //分类
        int[] equal = Arrays.stream(nums).filter(i -> i == pivot).toArray();
        int[] big = Arrays.stream(nums).filter(i -> i > pivot).toArray();
        int[] small = Arrays.stream(nums).filter(i -> i < pivot).toArray();

        if (k <= small.length) {
            //说明在小的里面
            return findKthLargestHelper(small, k, random);
        } else if (k > small.length + equal.length) {
            //说明在大的里面
            return findKthLargestHelper(big, k - small.length - equal.length, random);
        } else {
            return pivot;
        }

    }

    /**
     * 最大矩形面积
     *
     * @param heights 高度
     * @return int 面积的大小
     */
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        //计算结果 :最大的面积
        int res = 0;
        //使用栈来存储下标 且高度递增
        Deque<Integer> stack = new ArrayDeque<>(len);
        //在开始和结尾增加哨兵节点 0 方便计算
        len += 2;
        int[] newHeights = new int[len];
        System.arraycopy(heights, 0, newHeights, 1, len - 2);
        //放入第一个哨兵节点
        stack.push(0);
        //开始遍历
        for (int i = 1; i < len; i++) {
            while (newHeights[i] < newHeights[stack.peek()]) {
                //说明可以计算 ， 以当前栈里面存储高度为高的矩形的最大面积
                //高
                int height = newHeights[stack.pop()];
                // 宽：目标高度 左右两边不同高度的下标差为宽
                int width = i - stack.peek() - 1;
                res = Math.max(res, height * width);
            }
            stack.push(i);

        }

        return res;
    }

    /**
     * 每日温度
     *
     * @param temperatures 温度数组
     * @return 距离当天温度最近的高温
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        // arrayDeque 效率高于stack 高于LinkedList
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];
            while (!st.isEmpty() && t >= temperatures[st.peek()]) {
                st.pop();
            }
            if (!st.isEmpty()) {
                ans[i] = st.peek() - i;
            }
            st.push(i);
        }
        return ans;
    }

    /**
     * 简化路径
     * 变为更规范的形式
     *
     * @param path 路径
     * @return {@link String}
     */
    public String simplifyPath(String path) {
        Stack<String> stringStack = new Stack<>();
        //记录当前的单词
        String[] strings = path.split("/");
        for (int i = 0; i < strings.length; i++) {
            if (strings[i].equals("..")) {
                //出栈一个
                if (!stringStack.isEmpty()) {
                    stringStack.pop();
                }
            } else if (strings[i].equals(".") || strings[i].equals("")) {
                continue;
            } else {
                stringStack.push(strings[i]);
            }
        }
        return "/" + String.join("/", stringStack);
    }


}
